package test.tree;

import java.util.ArrayList;
import java.util.List;

import lombok.Data;

@Data
public class AVLTree {
	
	private TreeNode root;
	
	@Data
	private static class TreeNode {
		private int data;
		private TreeNode left;
		private TreeNode right;
		private TreeNode parent;
		private int height;
		private boolean isLeftChild;//是否是左孩子
		@Override
		public String toString() {
			return "TreeNode [data=" + data + ", left=" + (left==null?null:left.data)
					+ ", right=" + (right==null?null:right.data)
					+ ", parent=" + (parent==null?null:parent.data) 
					+ ", height=" + height
					+ "]";
		}
	}
	
	private void add(int data, TreeNode node) {
		TreeNode newNode = new TreeNode();
		newNode.data = data;
		
		TreeNode parent = null;
		while(true) {
			TreeNode left = node.left;
			TreeNode right = node.right;
			if(data < node.data) {
				if(left==null) {
					parent = node;
					node.left = newNode;
					newNode.isLeftChild = true;
					break;
				}
				node = left;
			} else if(data > node.data) {
				if(right==null) {
					parent = node;
					node.right = newNode;
					break;
				}
				node = right;
			} else {
				throw new RuntimeException("已存在[data=" + data + "]的节点!!!");
			}
		}
		
		newNode.parent = parent;
//		System.out.println(newNode);
//		processHeight(newNode);
		processBF(newNode);
	}
	
//	private void processHeight(TreeNode node) {
//		TreeNode parent = node.parent;
//		if(parent.left==null || parent.right==null) {
//			do {
//				parent.height++;
//				parent = parent.parent;
//			} while(parent!=null);
//		}
//	}
	
	/**
	 * 				  15(1)
	 * 			7(1|1)			23(1|0)
	 * 		3(2|1)	   11     19(2|0)   36(2|0)
	 * 	  1(3|0) 5()
	 * 	         
	 * @param node
	 */
	private void processBF(TreeNode node) {
		List<TreeNode> list = new ArrayList<>();
		while(node!=null) {
			calcNodeHeight(node);
			list.add(node);
			int leftHeight = node.left==null?-1:node.left.height;
			int rightHeight = node.right==null?-1:node.right.height;
			int bf = Math.abs(leftHeight - rightHeight);
			if(bf==2) {
				spin(list);
				break;
			}
			
			node = node.parent;
		}
	}
	
	/**
	 * 旋转
	 * @param node
	 */
	private void spin(List<TreeNode> list) {
		// node 是子节点 平衡因子大于2的是其父节点
		int size = list.size();
		TreeNode unbalanceNode = list.get(size - 1);
		TreeNode sonNode = list.get(size - 2);
		TreeNode grandsonNode = list.get(size - 3);
		TreeNode newNode = list.get(0);
		int data = sonNode.data;
		int pdata = unbalanceNode.data;
		int ndata = newNode.data;
		boolean isLeftChild = sonNode.isLeftChild;
		//是否要做双旋转
		boolean isDoubleSpin = (isLeftChild && (ndata > data) && (ndata < pdata))
				|| (!isLeftChild && (ndata > pdata) && (ndata < data));
		TreeNode axisNode = null; //轴节点
		if(isDoubleSpin) {
			//双旋转
			//轴节点为孙子节点
			axisNode = grandsonNode;
			boolean axisIsLeft= axisNode.isLeftChild;
			if(axisIsLeft) {
				//轴节点是左孩子，就先右旋转，再左旋转
				root = spinRightLeft(axisNode);
			} else {
				//轴节点是右孩子，就先左旋转，再右旋转
				root = spinLeftRight(axisNode);
			}
		} else {
			//单旋转
			//轴节点为子节点
			axisNode = sonNode;
			boolean axisIsLeft= axisNode.isLeftChild;
			if(axisIsLeft) {
				//轴节点是左孩子=》右旋转
				/**
				 * 			8(2) last                       5
				 * 		5(1) axis		12(0)             4    8
				 * 	  4(1) 7(0)                         3     7  12
				 *   3(0)                                            
				 */
				root = spinRight(axisNode);
			} else {
				//轴节点是右孩子=》左旋转
				/**
				 *       5(2) last                       8
				 *     3    8(1) axis                 5     12   
				 *        7    12(1)             3     7          14
				 *                 14(0)
				 */
				root = spinLeft(axisNode);
			}
		}
	}
	
	private TreeNode spinLeft(TreeNode axisNode) {
		TreeNode lastNode = axisNode.parent;
		
		lastNode.right = axisNode.left;
		axisNode.left = lastNode;
		
		axisNode.parent = lastNode.parent;
		if(lastNode.parent!=null) {
			lastNode.parent.left = axisNode;
		}
		lastNode.parent = axisNode;
		
		calcNodeHeight(axisNode);
		calcNodeHeight(lastNode);
		
		return axisNode;
	}
	
	private TreeNode spinRight(TreeNode axisNode) {
		TreeNode lastNode = axisNode.parent;
		
		lastNode.left = axisNode.right;
		axisNode.right = lastNode;
		
		axisNode.parent = lastNode.parent;
		if(lastNode.parent!=null) {
			lastNode.parent.right = axisNode;
		}
		lastNode.parent = axisNode;
		
		calcNodeHeight(axisNode);
		calcNodeHeight(lastNode);
		
		return axisNode;
	}
	
	private TreeNode spinLeftRight(TreeNode node) {
		spinLeft(node);
		return spinRight(node);
	}
	
	private TreeNode spinRightLeft(TreeNode node) {
		spinRight(node);
		return spinLeft(node);
	}
	
	private void calcNodeHeight(TreeNode node) {
		int leftHeight = node.left==null?-1:node.left.height;
		int rightHeight = node.right==null?-1:node.right.height;
		if(leftHeight==-1 && rightHeight==-1) {
			node.height = 0;
		} else {
			node.height = Math.max(leftHeight, rightHeight) + 1;
		}
	}
	
	public void add(int data) {
		if(root==null) {
			root = new TreeNode();
			root.data = data; 
		} else {
			add(data, root);
		}
	}
	
	public void add(int...datas) {
		for(int data : datas) {
			add(data);
		}
	}
	
	private TreeNode search(int data, TreeNode node) {
		while(node!=null) {
			if(data < node.data) {
				node = node.left;
			} else if(data > node.data) {
				node = node.right;
			} else {
				return node;
			}
		}
		return node;
	}
	
	public TreeNode search(int data) {
		if(root==null) {
			return null;
		}
		return search(data, root);
	}
	
	public void delete(int data) {
		TreeNode node = search(data);
		if(node!=null) {
			TreeNode parent = node.parent;
			if(parent==null) {
				root = null;
				return;
			}
			
			if(node.left!=null && node.right!=null) {
				/**
				 * 			15                 15
				 * 		11		18          13      18
				 * 	  5    14       20    5   14       20
				 * 1   8  13	         1  8          
				 */
				TreeNode successorNode = successor(node);
				node.data = successorNode.data;
				node = successorNode;
			}
			
			TreeNode child = null;
			TreeNode left = node.left;
			TreeNode right = node.right;
			if(node.left!=null) {
				child = left;
			} else if(node.right==null) {
				child = right;
			}
			
			boolean isLeftChild = node.isLeftChild;
			if(child==null) {
				if(isLeftChild) {
					node.parent.left = null;
				} else {
					node.parent.right = null;
				}
			} else {
				child.parent = node.parent;
				if(isLeftChild) {
					node.parent.left = child;
				} else {
					node.parent.right = child;
				}
			}
		}
	}
	
	/**
	 * 后继节点
	 * @param node
	 * @return
	 */
	private TreeNode successor(TreeNode node) {
		if(node.right!=null) {
			return min(node.right);
		}
		if(node.isLeftChild) {
			return node.parent;
		} else {
			//如果该节点是右孩子，往上找他的父节点直到是左孩子的父节点为止，后继节点就是这个父节点的父节点
			while(!node.parent.isLeftChild) {
				node = node.parent;
			}
			return node.parent.parent;
		}
	}
	
	private TreeNode min(TreeNode node) {
		while(node.left!=null) {
			node = node.left;
		}
		return node;
	}
	
	public static void main(String[] args) {
		AVLTree avl = new AVLTree();
		avl.add(8);
		
		
		avl.add(5);
		avl.add(12);
		avl.add(10);
		avl.add(13);
		
		System.out.println(avl.search(8));
		System.out.println(avl.search(5));
		System.out.println(avl.search(12));
		System.out.println(avl.search(10));
		System.out.println(avl.search(13));
//		avl.add(9);
//		System.out.println("------------------");
//		System.out.println(avl.search(10));
//		System.out.println(avl.search(8));
//		System.out.println(avl.search(12));
//		System.out.println(avl.search(5));
//		System.out.println(avl.search(9));
//		System.out.println(avl.search(13));
	}

}
